﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0062_ThreeSum : IAlgorithm
    {
        // 15. 三数之和

        // 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
        // 注意：答案中不可以包含重复的三元组。

        // 提示：
        //  0 <= nums.length <= 3000
        //  -10^5 <= nums[i] <= 10^5

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { -1, 0, 1, 2, -1, -4 };
            // 算法执行与打印
            var res = ThreeSum(nums);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem);
                }
                Console.WriteLine();
            }
            //Console.WriteLine();
        }

        // 算法
        public IList<IList<int>> ThreeSum(int[] nums)
        {
            var lists = new List<IList<int>>();
            // 排序
            Array.Sort(nums);
            // 双指针
            int len = nums.Length;
            for (int i = 0; i < len; ++i)
            {
                // 值大于0，后续只会更大不用看了。
                if (nums[i] > 0) 
                    break;
                // 跳过重复值
                if (i > 0 && nums[i] == nums[i - 1]) 
                    continue;
                // 获取当前值
                int curr = nums[i];
                // 设置左右指针，当前索引后一位，数组最后一位
                int L = i + 1, R = len - 1;
                while (L < R)
                {
                    // 三数和
                    int tmp = curr + nums[L] + nums[R];
                    // 和为0加入结果
                    if (tmp == 0)
                    {
                        var list = new List<int>
                        {
                            curr,
                            nums[L],
                            nums[R]
                        };
                        lists.Add(list);
                        // 跳过重复的左右指针
                        while (L < R && nums[L + 1] == nums[L]) 
                            ++L;
                        while (L < R && nums[R - 1] == nums[R]) 
                            --R;
                        ++L;
                        --R;
                    }
                    // 合小于零提高左指针值
                    else if (tmp < 0)
                    {
                        // 跳过重复的左指针
                        while (L < R && nums[L + 1] == nums[L])
                            ++L;
                        ++L;
                    }
                    // 和大于零降低右指针值
                    else
                    {
                        // 跳过重复的右指针
                        while (L < R && nums[R - 1] == nums[R])
                            --R;
                        --R;
                    }
                }
            }
            return lists;
        }
    }
}
